import { TreeNode } from "./00_二叉搜索树BSTree";
import { btPrint } from "hy-algokit";

class AVLTreeNode<T> extends TreeNode<T> {
  left: AVLTreeNode<T> | null = null;
  right: AVLTreeNode<T> | null = null;
  parent: TreeNode<T> | null = null;
  // 当前节点的高度
  height: number = 1;
  // 获取节点最大高度
  private getMaxHeight(): number {
    const leftHeight = this.left ? this.left.getMaxHeight() : 0;
    const rightHeight = this.right ? this.right.getMaxHeight() : 0;

    return Math.max(leftHeight, rightHeight) + 1;
  }

  // 获取平衡因子
  private getBalanceFactor(): number {
    const leftHeight = this.left ? this.left.getMaxHeight() : 0;
    const rightHeight = this.right ? this.right.getMaxHeight() : 0;

    return leftHeight - rightHeight;
  }

  // 判断是否平衡
  get isBalanced(): boolean {
    // -1 0 1就返回true
    return Math.abs(this.getBalanceFactor()) <= 1; // 平衡因子绝对值小于等于1
  }

  // 判断更高子节点
  get getHigherChild(): AVLTreeNode<T> | null {
    const leftHeight = this.left ? this.left.getMaxHeight() : 0;
    const rightHeight = this.right ? this.right.getMaxHeight() : 0;

    if (leftHeight > rightHeight) return this.left;
    if (leftHeight < rightHeight) return this.right;
    return this.isLeft ? this.left : this.right;
  }

  // 右旋转操作
  // rightRotate(): AVLTreeNode<T> | null {
  //   const pivot = this.left as AVLTreeNode<T>; // 确保类型一致
  //   if (!pivot) return null;

  //   // 更新父节点关系
  //   pivot.parent = this.parent;
  //   if (this.parent) {
  //     if (this.parent.left === this) {
  //       this.parent.left = pivot;
  //     } else if (this.parent.right === this) {
  //       this.parent.right = pivot;
  //     }
  //   }

  //   // 更新子节点关系
  //   this.left = pivot.right;
  //   if (pivot.right) {
  //     pivot.right.parent = this;
  //   }

  //   // 更新根节点关系
  //   pivot.right = this;
  //   this.parent = pivot;

  //   // 更新高度
  //   this.height = this.getMaxHeight();
  //   pivot.height = pivot.getMaxHeight();

  //   return pivot;
  // }

  // 右旋转操作
  rightRotation(): AVLTreeNode<T> | null {
    const isLeft = this.isLeft;
    const isRight = this.isRight;

    // 1. 找到左子节点的轴心点
    const pivot = this.left;
    // 2. 将轴心点的parent指向this的parent
    pivot!.parent = this.parent;

    // 3. 处理pivot的右子节点指向this
    this.left = pivot?.right || null;
    if (pivot?.right) {
      pivot.right.parent = this;
    }

    // 4. 处理this根节点, 将this的parent指向pivot
    pivot!.right = this;
    this.parent = pivot;

    // 5. pivot 成为根节点
    if (!pivot?.parent) {
      return pivot as AVLTreeNode<T>;
    } else if (isLeft) {
      // pivot是this的左子节点
      pivot.parent.left = pivot;
    } else if (isRight) {
      // pivot是this的右子节点
      pivot.parent.right = pivot;
    }

    return pivot as AVLTreeNode<T>;
  }
}

const root = new AVLTreeNode<number>(10);
root.left = new AVLTreeNode<number>(8);
root.left.parent = root;
root.left.left = new AVLTreeNode<number>(5);
root.left.left.parent = root.left;

const parent = new AVLTreeNode<number>(12);
parent.left = root;

root.parent = parent;

btPrint(parent);
console.log(root.rightRotation());

btPrint(parent);

export {};
